package com.huangkailong.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。<br/>
 * <br/>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。<br/>
 * <br/>
 * <br/>
 * <br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * 输入：digits = "23"<br/>
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]<br/>
 * 示例 2：<br/>
 * <br/>
 * 输入：digits = ""<br/>
 * 输出：[]<br/>
 * 示例 3：<br/>
 * <br/>
 * 输入：digits = "2"<br/>
 * 输出：["a","b","c"]<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * 0 <= digits.length <= 4<br/>
 * digits[i] 是范围 ['2', '9'] 的一个数字。<br/>
 * <br/>
 * @author huangkl
 * @since 1.0.0
 */
public class LetterCombinations {
    /**
     * 回溯
     */
    public static List<String> solution1(String digits){
        List<String> result = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return result;
        }
        Map<Character, String> digitLettersMap = new HashMap<>();
        digitLettersMap.put('2', "abc");
        digitLettersMap.put('3', "def");
        digitLettersMap.put('4', "ghi");
        digitLettersMap.put('5', "jkl");
        digitLettersMap.put('6', "mno");
        digitLettersMap.put('7', "pqrs");
        digitLettersMap.put('8', "tuv");
        digitLettersMap.put('9', "wxyz");

        doLetterCombinations(digitLettersMap, result, new StringBuilder(), digits, 0);
        return result;
    }

    public static void doLetterCombinations(Map<Character, String> digitLettersMap,
                                     List<String> result,
                                     StringBuilder resultSb,
                                     String digits,
                                     int digitIndex){
        if(digitIndex == digits.length()){
            result.add(resultSb.toString());
            return;
        }

        String letters = digitLettersMap.get(digits.charAt(digitIndex));
        for (int i = 0; i < letters.length(); i++) {
            resultSb.append(letters.charAt(i));
            doLetterCombinations(digitLettersMap, result, resultSb, digits, digitIndex+1);
            resultSb.deleteCharAt(digitIndex);
        }
    }
}
